1. Field of the Invention
The present invention relates to a system and method for decoding an encoded data stream.
2. Description of the Prior Art
Bit errors can often arise when transmitting data across a medium, such as radio, infra-red, via a hard disk""s magnetic head, etc. Accordingly, it is known to encode data prior to transmission so as to add redundancy to the original data before it is transmitted. A suitable decoder is then used when the data stream is received to decode the encoded data stream, with the redundancy providing some resilience to bit errors. Of course, the more redundancy added during encoding, the more bits that need to be transmitted, and accordingly, a balance is necessary between the amount of redundancy added, and the amount of resilience to bit errors achieved as a result of the addition of the redundancy.
One common encoding technique is often referred to as convolutional encoding, which produces an encoded data stream comprising a plurality of codes. Whenever the encoder receives an input to be encoded, e.g. a data bit, it generates a code dependent on the received input, and a number of previous inputs received by the encoder. A term called xe2x80x9cconstraint lengthxe2x80x9d is used to indicate the number of inputs that a convolutional encoder uses in order to generate an output code. For example, if the constraint length xe2x80x9ckxe2x80x9d is 7, this means that the output code generated by the convolutional encoder is dependent on the current input, plus the previous 6 inputs. Accordingly, it will be appreciated that for each input, there are 2k-1 previous states that the encoder could be in.
There are many different uses for the above type of encoding, for example in hard disk drives, mobile phones, and Digital Audio Broadcast (DAB) radio. One example of a standard relating to DAB is the ETSI (European Telecommunications Standard Institute) ETS 300 401 May 1997 (Second Edition) standard entitled xe2x80x9cRadio Broadcasting Systems;Digital Audio Broadcasting (DAB) to mobile, portable and fixed receiversxe2x80x9d. In DAB radio, the constraint length k of the encoder is 7, so, for each input bit, there are 64 states that the encoder could be in (based on the 6 previous input bits).
When an original sequence of data bits has been encoded to form an encoded data stream, it will be appreciated that a technique needs to be provided at the receiving end for decoding the data stream and using the redundancy therein to seek to correct any errors in the information received. One algorithm often used to perform such decoding is the Viterbi algorithm which is typically used to decode convolutionally encoded data streams. A general description of the Viterbi algorithm is given in the publication xe2x80x9cDigital Communicationsxe2x80x9d by John G. Proakis (Third Edition). McGraw-Hill Inc.
In accordance with the Viterbi technique, a table such as that illustrated in FIG. 1 is generated, which has an entry for each of the 2k-1 states, and which is updated upon receipt of each code in the encoded data stream, Hence, as illustrated in FIG. 1, each entry will have a field 20 identifying the state, a field 30 identifying a xe2x80x9cmetricxe2x80x9d or score associated with that state, and a path history 40 giving an indication of a predetermined number of bits that are considered to be bits in the original data sequence assuming the associated state is the most likely state.
When each code is received, the metric 30 for each of the states must be updated, and the state with the xe2x80x9cbestxe2x80x9d metric (e.g. typically the one with either the lowest or the highest value depending on the implementation) is selected as having the correct path. Accordingly, the oldest bit in that state""s path history 40 is then output as the correct output bit for this stage.
To indicate how the metrics are typically updated for each state, reference will be made to FIG. 2, which indicates how a new state is related to a previous state. It will be appreciated that, assuming a particular state is correct, then when a new bit is received by the encoder, that bit will either be a logic zero value or a logic one value, and accordingly there are two possibilities as to the data used to generate the code output by the encoder. Due to the possibility of corruption of the signal, it will be appreciated that, when a code is received at the decoder, it is necessary to determine, for each state in the table 10, the likelihood that that state represents the k-1 previous input bits used along with a new input bit to generate the code.
With reference to FIG. 2, this illustrates the possible states assuming the constraint length k is 4, and that accordingly three preceding input bits are used along with a new input bit to generate a code. On the left hand side of the diagram, it will be seen that all of the eight possible states of the three preceding bits are indicated. Considering the example of the old state being 001, it will be appreciated that the data upon which the code generated by the encoder was based would either be 0010 or 0011, i.e. the new bit can only be 0 or 1. The decoder knows what the code generated by the encoder would have been had the bits in fact been 0010 or 0011. and can accordingly compare those codes with the code received to determine the likelihood that the bits used to generate the transmitted code were in fact 0010 or 0011. This comparison yields an update value (often referred to as a Hamming distance) which can be used to generate an updated score for the state.
As is also apparent from FIG. 2, although once the code has been processed, there are still the same set of states in the table 10, the way in which these states are related to the old states is quite complex. For example, the new state 010 may have arisen from the previous states 001 or 101, in both cases with the new bit received being a 0. Hence, Hamming distances can be generated for each possibility based on comparing the code received with the code expected for 0010 and 1010, respectively. Then the metric associated with the old state 001 is retrieved, and the corresponding Hamming distance is added to that metric, resulting in a possible updated metric. This process is repeated for the metric associated with the state 101, whereby two possible metrics for the new state 010 have now been calculated. Whichever of the two possible metrics is deemed best (for example, the one with the smallest value if the Hamming distance is defined to increase as the match between the two codes gets worse) is selected, and used as the new metric for state 010. In addition, the relevant bit is added to the relevant path history. For example, if state 010 is deemed to have arisen from state 001, it can be seen that logic 0 value should be added to the path history for 001. This path history is then copied to the state 010 as the new path history for that state. Alternatively, if state 010 is deemed to have arisen from state 101, it can be seen that a logic 1 value should be added to the path history for state 101, and this path history then copied to the state 010 as the new path history for that state.
The above process is performed for each of the states in the table 10, with the end result being that each of the metrics 30 and path histories are updated. Further, if the path history is already full, then the oldest bit in the path history associated with the state having the best metric may be output at this time as the bit considered to be the correct bit in the original data sequence.
Given the above description, it will be appreciated that for each state update, two metrics (often metrics from different states to the state being updated) need to be added to two Hamming distances (which are dependent on the code received) and the smaller of the two (assuming a smaller distance is better) is selected and then stored in association with the state being updated. Later, when output bits are required from the decoder, all of the metrics are compared, and the state with the best metric is deemed to have associated therewith the path which is closest to the original data.
From the above description, it will be appreciated that a significant amount of processing needs to be performed to determine each state update, since as mentioned above each state update requires two metrics to be added to two Hamming distances, for the two results to be compared, and one of them selected. This process then needs to be repeated for each state in the table 10.
Accordingly, it is an object of the present invention to provide an improved technique for updating the metrics for each state.
Viewed from a first aspect, the present invention provides a method of decoding an encoded data stream representing an original sequence of data bits, wherein the encoded data stream comprises a plurality of codes, each code being dependent on a current data bit and a first predetermined number of preceding data bits in the original sequence, the method comprising the steps of. (a) for each of a number of possible states of the first predetermined number of preceding data bits, providing a score indicating the likelihood that the corresponding state represents the first predetermined number of preceding data bits; (b) arranging the scores in an initial ordering; (c) receiving a code; (d) given each of the two possible values of the current data bit in the received code, determining for each state two update values indicating the likelihood, based on the received code, that that state represents the first predetermined number of bits; (e) storing a first plurality of score bit slices to collectively represent the scores as arranged at said step (b), each score bit slice containing a predetermined bit from each of the scores; (f) reordering the scores and storing a second plurality of score bit slices to collectively represent the reordered scores, each score bit slice containing a predetermined bit from each of the reordered scores; (g) generating from the update values a first plurality of update bit slices for the first plurality of score bit slices and a second plurality of update bit slices for the second plurality of score bit slices, each update bit slice representing a predetermined bit from predetermined ones of said update values; (h) generating a first candidate plurality of updated score bit slices from the first plurality of score bit slices and the first plurality of update bit slices, and generating a second candidate plurality of updated score bit slices from the second plurality of score bit slices and the second plurality of update bit slices; (i) generating a plurality of updated score bit slices by, for each score represented by the bit slices, applying predetermined criteria to select the bits for that score from either the first candidate or the second candidate plurality of updated score bit slices; whereby all the scores are updated simultaneously.
Rather than updating the score for each state one at a time, the present invention enables the scores for all states to be updated simultaneously. In the conventional prior art approaches, each score is stored in a separate word, but in accordance with the present invention the simultaneous update of the scores is achieved by xe2x80x9cbit slicingxe2x80x9d the relevant values required in the calculations. Hence, in accordance with preferred embodiments of the present invention, the lowest significant bit of the scores for every state are held together in a single word (which, depending on the number of states, may consist of multiple machine words, e.g. multiple 32-bit machine words), the next most significant bit of the scores for all the states are held in another word, and so on. Therefore, considering an example where each score is required to have eight bits of precision, then there will typically be provided eight bit slices to hold all of the scores. This bit slicing technique is illustrated by way of example with reference to the following two tables, where Table 1 illustrates the conventional technique where the scores a, b, c, d, . . . z are stored in separate words, and Table 2 shows the bit slicing technique of preferred embodiments, where each word (xe2x80x9cbit slicexe2x80x9d) contains a predetermined bit from each of the scores:
In accordance with the present invention, a first plurality of score bit slices are stored based on an initial ordering of the scores. However, as mentioned earlier with reference to FIG. 2, there are two possible routes for updating any particular state. In accordance with the present invention, this issue is addressed by re-ordering the scores and storing a second plurality of score bit slices to collectively represent the re-ordered scores, such that two separate plurality of score bit slices are then stored.
Further, in accordance with the present invention, the update values (for example Hamming distances) are also stored as bit slices, with a first plurality of update bit slices being generated for the first plurality of score bit slices and a second plurality of update bit slices being generated for the second plurality of score bit slices.
Then, a first candidate plurality of updated score bit slices is generated from the first plurality of score bit slices and the first plurality of update bit slices, and similarly a second candidate of updated score bit slices is generated from the second plurality of score bit slices and the second plurality of update bit slices. In preferred embodiments, these candidate plurality of updated score bit slices are generated by adding the corresponding plurality of score bit slices and corresponding plurality of update bit slices together.
In accordance with the present invention, a final step is then employed which applies predetermined criteria to determine for each individual score whether that score should be selected from the first candidate plurality of updated score bit slices or the second candidate plurality of updated score bit slices. This results in the generation of a final plurality of updated score bit slices which reflects all of the updated scores, whereby it can be seen that all of the scores are updated simultaneously.
In preferred embodiments, the method of the present invention is implemented in software, and due to the simultaneous updating of all of the scores has been found to offer significant potential speed improvements over the known prior art techniques.
In preferred embodiments, upon receipt of a further code from the encoded data stream, the plurality of updated score bit slices are treated as the first plurality of score bit slices and steps (f) to (i) are repeated, with the update values used in step (g) being based on the further code.
In the known prior art systems, as described earlier with reference to FIG. 2, the metrics are not written back to the same state which they are read from, and indeed some metrics can be duplicated. For this reason, the traditional prior art techniques use two banks of metrics and path histories. One set is used to write into and the other set is used to read from. Once all of the states have been updated, then they are swapped. In these prior art techniques, the positions of the states stay the same, and the metrics are moved. For a particular state n and a N state Viterbi:
metric[n*2] comes from either metric[n] or metric [n+N/2].
metric[n*2+1] comes from either metric[n] or metric [n+N/2].
This can for example be seen to be the case from the example of FIG. 2, where N is 8 and n varies from 0 to 7.
Hence, it would appear that the storing of the scores as a plurality of bit slices would lead to a number of complications, since at the end of each update, all of the bits in each bit slice would need to be moved around. However, in accordance with the preferred embodiments of the present invention, on each iteration, the plurality of updated score bit slices are treated as the first plurality of score bit slices without any rearrangement of the bits in each bit slice, and the scores are only re-ordered to form the second plurality of score bit slices. In such preferred embodiments, it has been found that, assuming each code is dependent on k bits, then although during each iteration of steps (f) to (i) the states represented by individual scores contained within the plurality of updated score bit slices change, the scores return to the initial ordering following k-1 iterations of the steps (t) to (i). Hence, by this approach, rather than keeping the states in the same place as is the case with known prior art techniques, at least one of the sets of metrics stays in the same place, and the nominal states which that metric represents change during each iteration. However, within a relatively short number of iterations, the scores return to the initial ordering.
In preferred embodiments, a record is maintained of the states represented by the individual scores for each of the k-1 iterations. Hence, with a knowledge of which iteration is being performed, it is possible to determine which state any particular score is associated with.
In preferred embodiments, the re-ordering of the scores at the step (f) is dependent on the particular iteration. However, since in preferred embodiments, no re-ordering of the first plurality of score bit slices takes place, it has been found that the re-ordering of the scores in order to form the second plurality of score bit slices involves merely a linear re-ordering of metrics, rather than the complex fanning out movement illustrated earlier with reference to FIG. 2. Hence, it has been found that in the preferred embodiments of the present invention, the number of operations required to perform the re-ordering is significantly less than that required having regard to the complex re-ordering that would be indicated by the known prior art techniques.
In preferred embodiments, step (d) is executed prior to decoding the encoded data stream in order to generate a lookup table of update bit slices for each of the k-1 iterations, whereby at said step (g) the update bit slices are read from the lookup table based on the received code, the iteration, and an indication of whether the update bit slices are for the first or the second plurality of score bit slices. Since in preferred embodiments, the scores return to the initial ordering following k-1 iterations, then it is clear that there are only a finite number of possibilities for the update bit slices. Hence, it is possible to generate a lookup table providing all of the possible update bit slices, thereby removing the need to generate those update bit slices during the decoding process. The size of the lookup table will depend on the number of possible received codes, the number of iterations, and the number of bit slices required to represent an update value. However, for practical examples such as DAB radio, it has been found that the lookup table is of a fairly modest size. For example, considering DAB radio, k=7, and hence the number of iterations is 6. Further, the codes are four bits in length, and accordingly it has been found that the update values can be represented by three bits, and thus only three bit slices are required. This results in 288 (16 codesxc3x976 stagesxc3x973 bit slices) update bit slices needing to be stored in the lookup table for each of the first and second plurality of score bit slices used in the update process, or 576 update bit slices in total.
In preferred embodiments, the step (i) comprises the step of subtracting the second candidate plurality of updated score bit slices from the first candidate plurality of updated score bit slices to form a path history bit slice, the bits for a particular score represented by the plurality of updated score bit slices being selected dependent on the value of the bit at a corresponding position in the path history bit slice. In preferred embodiments, the path history bit slice contains the carry out values from the subtraction. Hence, if the first plurality of updated score bit slices is represented by MA, and the second candidate plurality of updated score bit slices is represented by MB, then a zero value at a particular position in the path history bit slice will indicate that the corresponding score in MA was bigger than the corresponding score in MB, whereas a logic one value will indicate that the corresponding score in MB was greater than the corresponding score in MA. Hence, based on the values in the path history bit slice, it will be appreciated that it can then be determined which score to use in the final plurality of updated score bit slices generated at step (i).
In preferred embodiments, the path history bit slice is added to a path history consisting of a number of path history bit slices, the path history being employed to determine for any particular state a second predetermined number of bits that are considered to be bits in the original sequence preceding the first predetermined number. In such embodiments, it will be appreciated that there is no need to refer to the previous path history bit slices at this stage, and accordingly the path history bit slice can merely be added to the path history without having to read any of the previous path history bit slices at that point. This is a particularly efficient way of updating the path history.
It will be appreciated that because the individual path histories are not being moved during each iteration, and the states have been allowed to move around (because at least one of the plurality of score bit slices is not re-ordered) then it would appear to be cumbersome to trace back the path history for any particular state. However in preferred embodiments, each path history bit slice is associated with one of said k-1 iterations, whereby with reference to said record the second predetermined number of bits can be determined for any particular state. Hence, it is clear that the necessary information is available to enable the trace back to occur. Further, it has been found that in preferred embodiments if the path history is allowed to become longer than it might otherwise be, then the trace back can be delayed until there are a large number of bits to output, so that the overhead of the trace back becomes lower per output bit. It is important to note that in the preferred embodiments of the present invention, the performance of updating the path history is not effected by the extra length of the path history, as the path history is updated merely by adding a new path history bit slice, without any requirement to read the path history at that stage.
Hence, in preferred embodiments, at predetermined intervals, the scores are compared in order to select the score best meeting predetermined criteria, the state corresponding to that score is determined, and a plurality of said second predetermined number of bits for that state are determined and output as a decoded portion of the original sequence of data bits.
Viewed from a second aspect, the present invention provides a system for decoding an encoded data stream representing an original sequence of data bits, wherein the encoded data stream comprises a plurality of codes, each code being dependent on a current data bit and a first predetermined number of preceding data bits in the original sequence, the system comprising: a score generator for providing, for each of a number of possible states of the first predetermined number of preceding data bits, a score indicating the likelihood that the corresponding state represents the first predetermined number of preceding data bits; a sorter for arranging the scores in an initial ordering; an update value generator, responsive to receipt of a code, for determining for each state, given each of the two possible values of the current data bit in the received code, two update values indicating the likelihood, based on the received code, that that state represents the first predetermined number of bits; the score generator being arranged to collectively represent the initially ordered scores as a first plurality of score bit slices each score bit slice containing a predetermined bit from each of the scores; the sorter being arranged to reorder the scores and the score generator being arranged to collectively represent the reordered scores as a second plurality of score bit slices, each score bit slice containing a predetermined bit from each of the reordered scores; the update value generator being arranged to generate from the update values a first plurality of update bit slices for the first plurality of score bit slices and a second plurality of update bit slices for the second plurality of score bit slices, each update bit slice representing a predetermined bit from predetermined ones of said update values; the score generator being arranged to generate a first candidate plurality of updated score bit slices from the first plurality of score bit slices and the first plurality of update bit slices, to generate a second candidate plurality of updated score bit slices from the second plurality of score bit slices and the second plurality of update bit slices, and to generate a plurality of updated score bit slices by, for each score represented by the bit slices, applying predetermined criteria to select the bits for that score from either the first candidate or the second candidate plurality of updated score bit slices, whereby all the scores are updated simultaneously.
Viewed from a third aspect, the present invention provides a computer program operable to configure a computer processing unit to perform a method as claimed in accordance with the first aspect of the present invention. It will be appreciated that the term xe2x80x9ccomputer processing unitxe2x80x9d is intended to cover any computing device that is capable of executing the computer program, and hence, for example, may be a conventional microprocessor, a dedicated logic unit, etc.
Viewed from a fourth aspect, the present invention provides a carrier medium comprising a computer program in accordance with the third aspect of the present invention. The carrier medium may be a storage device, for example a CD-ROM, a diskette, RAM, ROM, etc. Alternatively, the carrier medium may be any other medium via which the computer program is conveyed, for example telecommunications infrastructures facilitating electronic distribution of the computer program over the Internet.